class Solution:
    def trap(self, height):
        n = len(height)
        pre_max = [0] * n
        end_max = [0] * n
        ans = 0

        pre_max[0] = height[0]
        for i in range(1,n):
            pre_max[i] = max(pre_max[i-1],height[i])
        
        end_max[-1] = height[-1]
        for i in range(n-2, -1, -1):
            end_max[i] = max(end_max[i+1], height[i])
        for h,j, k in zip(height, pre_max, end_max):
            ans += min(k,j) -h
        
        return ans

height = [4,2,0,3,2,5]
print(Solution().trap(height))